//
// Created by Administrator on 2021/11/11.
// May Saint Diana bless you!
//
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int findTheWinner(int n, int k) {
        vector<int> list(n, 0);
        for (int i = 0; i < n; ++i) {
            list[i] = i + 1;
        }
        int pos = 0;
        while (list.size() > 1) {
            pos += k - 1;
            if (pos >= list.size()) {
                pos = pos % (int) list.size();
            }
            list.erase(list.begin() + pos);
        }
        return list[0];
    }

    int findTheWinner2(int n, int k) {
        // 找结果在前后两次变换之间的位置关系
        int luckier = 1;
        for (int i = 2; i <= n; i++) {
            luckier = ((luckier + k - 1) % i) + 1;
        }
        return luckier;
    }

    int findTheWinner3(int n, int k) {
        return f(n, k) + 1; // 答案从1开始
    }

    int f(int n, int k) {
        if (n == 1)
            return 0;
        return (f(n - 1, k) + k) % n;
    }


};

int main() {
    Solution solution;
    cout << solution.findTheWinner2(5, 2) << endl;
    cout << solution.findTheWinner2(6, 5) << endl;
    return 0;
}


